class Solution {
public:
    bool isValid(vector<vector<char> >& board,int row,int col,char c){
      for(int j = 0;j < board[0].size();j++){
        if(board[row][j] == c){
          return false;
        }
      }
      for(int i = 0;i < board.size();i++){
        if(board[i][col] == c){
          return false;
        }
      }
      int x = row / 3 * 3;
      int y = col / 3 * 3;
      for(int i = x;i < x + 3;i++){
        for(int j = y;j < y + 3;j++){
          if(board[i][j] == c){
            return false;
          }
        }
      }
      return true;
    }
    bool backtracking(vector<vector<char> >& board){
      for(int i = 0;i < board.size();i++){
        for(int j = 0;j < board[0].size();j++){
          if(board[i][j] != '.'){
            continue;
          }
          // char c = x + '0';
          // if(isValid(board,i,j,c) == true){
          //   board[i][j] = c;
          //   backtracking(board,1);
          // }else{
          //   backtracking(board,x+1);  
          //   board[i][j] = '.';
          // }
          for(char c = '1';c <= '9';c++){
            if(isValid(board,i,j,c)){
              board[i][j] = c;
              if(backtracking(board) == true){
                return true;
              }
              board[i][j] = '.';
            }
          }
          return false;
        }
      }
      return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
      backtracking(board);
    }
};
